package com.zjj.algorithm.learning.dmsxl.other;

/**
 * 941. 有效的山脉数组 简单题
 * <p>
 * 给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。
 * <p>
 * 让我们回顾一下，如果 arr 满足下述条件，那么它是一个山脉数组：
 * <p>
 * arr.length >= 3
 * 在 0 < i < arr.length - 1 条件下，存在 i 使得：
 * arr[0] < arr[1] < ... arr[i-1] < arr[i]
 * arr[i] > arr[i+1] > ... > arr[arr.length - 1]
 * <p>
 * <p>
 * <p>
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：arr = [2,1]
 * 输出：false
 * 示例 2：
 * <p>
 * 输入：arr = [3,5,5]
 * 输出：false
 * 示例 3：
 * <p>
 * 输入：arr = [0,3,2,1]
 * 输出：true
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= arr.length <= 104
 * 0 <= arr[i] <= 104
 *
 * @author zjj_admin
 * @date 2023/2/1 17:20
 */
public class Other_02_ValidMountainArray {


    public static void main(String[] args) {
        int[] arr = new int[]{2, 5, 2};
        boolean res = validMountainArray(arr);
        System.out.println("res = " + res);
    }


    /**
     * 时间
     * 2 ms
     * 击败
     * 17.47%
     * 内存
     * 42.7 MB
     * 击败
     * 14.31%
     *
     * @param arr
     * @return
     */
    public static boolean validMountainArray(int[] arr) {
        int len = arr.length;
        if (len < 3) {
            return false;
        }
        int[] temp = new int[]{0, 0};
        for (int i = 1; i < arr.length; i++) {
            //差值
            int X = arr[i] - arr[i - 1];
            if (i == 1) {
                if (X > 0) {
                    temp[0] = 1;
                } else {
                    return false;
                }
            } else {
                if (X == 0) {
                    return false;
                } else if (X > 0) {
                    if (temp[1] == -1) {
                        return false;
                    }
                } else {
                    temp[1] = -1;
                }
            }
        }
        return temp[1] == -1;
    }


    public static boolean validMountainArray2(int[] arr) {
        if (arr.length < 3) {
            return false;
        }
        // 双指针
        int left = 0;
        int right = arr.length - 1;
        // 注意防止指针越界
        while (left + 1 < arr.length && arr[left] < arr[left + 1]) {
            left++;
        }
        // 注意防止指针越界
        while (right > 0 && arr[right] < arr[right - 1]) {
            right--;
        }
        // 如果left或者right都在起始位置，说明不是山峰
        if (left == right && left != 0 && right != arr.length - 1) {
            return true;
        }
        return false;
    }
}
